#define _CRT_SECURE_NO_WARNINGS 1
#include<iostream>

using namespace std;


struct ListNode
{
	int val;
	struct ListNode* next;
	ListNode(int x)
		:val(x)
		, next(nullptr)
	{

	}
};

#include <cstddef>
namespace lh
{
	//BM1 反转链表
	//https://www.nowcoder.com/practice/75e878df47f24fdc9dc3e400ec6058ca?tpId=295&tqId=23286&ru=/exam/oj&qru=/ta/format-top101/question-ranking&sourceUrl=%2Fexam%2Foj%3Fpage%3D1%26tab%3D%25E7%25AE%2597%25E6%25B3%2595%25E7%25AF%2587%26topicId%3D295

	class Solution {
	public:
		ListNode* ReverseList(ListNode* pHead) {
			ListNode* head = nullptr;
			ListNode* cur = pHead;
			//头插迭代法
			while (cur != nullptr)
			{
				//记录当前结点下一个位置
				ListNode* next = cur->next;
				//每次只翻转一个结点
				cur->next = head;
				//要翻转的位置后移
				head = cur;
				cur = next;
			}
			return head;
		}
	};

	void test1()
	{
		ListNode* head=new ListNode(1);
		ListNode* node2=new ListNode(2);
		ListNode* node3=new ListNode(3);
		head->next = node2;
		node2->next = node3;
		//遍历链表
		ListNode* cur = head;
		while (cur != nullptr)
		{
			cout << cur->val << "->";
			cur = cur->next;
		}
		cout << endl;
		ListNode*phead=Solution().ReverseList(head);
		//遍历链表
		cur = phead;
		while (cur != nullptr)
		{
			cout << cur->val << "->";
			cur = cur->next;
		}
		cout << endl;
	}

	//BM2 链表内指定区间反转
	//https://www.nowcoder.com/practice/b58434e200a648c589ca2063f1faf58c?tpId=295&tqId=654&ru=/exam/oj&qru=/ta/format-top101/question-ranking&sourceUrl=%2Fexam%2Foj%3Fpage%3D1%26tab%3D%25E7%25AE%2597%25E6%25B3%2595%25E7%25AF%2587%26topicId%3D295
	class Solution2 {
	public:
		/**
		 *
		 * @param head ListNode类
		 * @param m int整型
		 * @param n int整型
		 * @return ListNode类
		 */
		ListNode* reverseBetween(ListNode* head, int m, int n) {
			//哨兵位
			ListNode* phead = new ListNode(0);
			phead->next = head;
			//m前一个结点
			ListNode* prev = phead;
			//当前结点
			ListNode* cur = head;
			for (int i = 1; i < m; i++)
			{
				prev = cur;
				cur = cur->next;
			}
			//当前结点的下一个结点
			ListNode* tmp = cur->next;
			//遍历翻转结点，cur和tmp交换位置(tmp位置到prev后)prev下一个必定指向tmp，tmp再移到cur后一个
			for (int i = m; i < n; i++)
			{
				//当且结点指向tmp后结点,移动cur
				cur->next = tmp->next;
				//tmp结点指向prev后结点，连接链表
				tmp->next = prev->next;
				//移动tmp结点，把tmp结点放前面
				prev->next = tmp;
				//更新tmp
				tmp = cur->next;
			}
			return phead->next;
		}
	};
	void test2()
	{
		int m = 2, n = 4;
		ListNode* head = new ListNode(1);
		ListNode* node2 = new ListNode(2);
		ListNode* node3 = new ListNode(3);
		ListNode* node4 = new ListNode(4);
		ListNode* node5 = new ListNode(5);

		head->next = node2;
		node2->next = node3;
		node3->next = node4;
		node4->next = node5;
		//遍历链表
		ListNode* cur = head;
		while (cur != nullptr)
		{
			cout << cur->val << "->";
			cur = cur->next;
		}
		cout << endl;
		ListNode* phead = Solution2().reverseBetween(head, m, n);

		cur = phead;
		while (cur != nullptr)
		{
			cout << cur->val << "->";
			cur = cur->next;
		}
		cout << endl;
	}

	//BM3 链表中的节点每k个一组翻转
	//https://www.nowcoder.com/practice/b49c3dc907814e9bbfa8437c251b028e?tpId=295&tqId=722&ru=/exam/oj&qru=/ta/format-top101/question-ranking&sourceUrl=%2Fexam%2Foj%3Fpage%3D1%26tab%3D%25E7%25AE%2597%25E6%25B3%2595%25E7%25AF%2587%26topicId%3D295
	class Solution3 {
	public:
		/**
		 *
		 * @param head ListNode类
		 * @param k int整型
		 * @return ListNode类
		 */
		ListNode* reverseKGroup(ListNode* head, int k) {
			//记录每段的尾结点(头结点翻转后就是尾结点)
			ListNode* tail = head;
			//遍历k个结点到达尾部(下一段未翻转的头)
			for (int i = 0; i < k; i++)
			{
				//不足k个直接不翻转返回头
				if (tail == nullptr)
				{
					return head;
				}
				tail = tail->next;
			}
			//同GM1 对当前段进行翻转
			//记录前一个结点和当前结点
			ListNode* prev = nullptr;
			ListNode* cur = head;
			//cur走到尾
			while (cur != tail)
			{
				//保存后续链表
				ListNode* tmp = cur->next;
				//断开链表翻转连接前一个结点
				cur->next = prev;
				//更新prev和cur(后移)
				prev = cur;
				cur = tmp;
			}
			//递归(头变为翻转后的尾，用来连接下一段链表)
			//此时tail是上一段链表的尾(1->2->tail),下一段的头
			head->next = reverseKGroup(tail, k);
			//最终prev为翻转后的头结点
			return prev;
		}
		
	};
	void test3()
	{
		ListNode* head = new ListNode(1);
		ListNode* node2 = new ListNode(2);
		ListNode* node3 = new ListNode(3);
		ListNode* node4 = new ListNode(4);
		ListNode* node5 = new ListNode(5);

		head->next = node2;
		node2->next = node3;
		node3->next = node4;
		node4->next = node5;
		//遍历链表
		ListNode* cur = head;
		while (cur != nullptr)
		{
			cout << cur->val << "->";
			cur = cur->next;
		}
		cout << endl;
		int k = 3;
		ListNode* phead = Solution3().reverseKGroup(head, k);

		cur = phead;
		while (cur != nullptr)
		{
			cout << cur->val << "->";
			cur = cur->next;
		}
		cout << endl;
	}

};


int main()
{
	//lh::test1();
	//lh::test2();
	lh::test3();

	return 0;
}